Wireless Local Area Networks (WLANS)
Wireless local area networks (WLANs) generally operate at peak speeds of between 10 to 100 Mbps and have a typical range of 100 meters. Single-cell Wireless LANs, as shown in FIG. 1A, are suitable for small single-floor offices or stores. A station in a wireless LAN can be a personal computer, a bar code scanner, or other mobile or stationary device that uses a wireless network interface card (NIC) to make the connection over the RF link to other stations in the network. The single-cell wireless LAN 100 of FIG. 1A provides connectivity within radio range between wireless stations 102, 104A, 104B, 106, and 108. Access point 108 allows connections via the backbone network 110 to wired network-based resources, such as servers. A single-cell wireless LAN can typically support up to 25 users and still keep network access delays at an acceptable level. Multiple-cell wireless LANs provide greater range than does a single-cell, by means of a set of access points and a wired network backbone to interconnect a plurality of single-cell LANs. Multiple-cell wireless LANs can cover larger multiple-floor buildings. A mobile laptop computer or data collector with a wireless network interface card (NIC) can roam within the coverage area while maintaining a live connection to the backbone network 11.
Wireless LAN specifications and standards include the IEEE 802.11 Wireless LAN Standard and the HIPERLAN Type 1 and Type 2 Standards. The IEEE 802.11 Wireless LAN Standard is published in three parts as IEEE 802.11-1999; IEEE 802.11a-1999; and IEEE 802.11b-1999, which are available from the IEEE, Inc. web site http://grouper.ieee.org/groups/802/11. An overview of the HIPERLAN Type 1 principles of operation is provided in the publication HIPERLAN Type 1 Standard, ETSI ETS 300 652, WA2 December 1997. An overview of the HIPERLAN Type 2 principles of operation is provided in the Broadband Radio Access Networks (BRAN), HIPERLAN Type 2; System Overview, ETSI TR 101 683 VI.I.1 (2000-02) and a more detailed specification of its network architecture is described in HIPERLAN Type 2, Data Link Control (DLC) Layer; Part 4. Extension for Home Environment, ETSI TS 101 761-4 V1.2.1 (2000-12). A subset of wireless LANs is Wireless Personal Area Networks (PANs), of which the Bluetooth Standard is the best known. The Bluetooth Special Interest Group, Specification Of The Bluetooth System, Version 1.1, Feb. 22, 2001, describes the principles of Bluetooth device operation and communication protocols.
The IEEE 802.11 Wireless LAN Standard defines at least two different physical (PHY) specifications and one common medium access control (MAC) specification. The IEEE 802.11(a) Standard is designed to operate in unlicensed portions of the radio spectrum, usually either in the 2.4 GHz Industrial, Scientific, and Medical (ISM) band or the 5 GHz Unlicensed-National Information Infrastructure (U-NII) band. It uses orthogonal frequency division multiplexing (OFDM) to deliver up to 54 Mbps data rates. The IEEE 802.11(b) Standard is designed for the 2.4 GHz ISM band and uses direct sequence spread spectrum (DSSS) to deliver up to 11 Mbps data rates. The IEEE 802.11 Wireless LAN Standard describes two major components, the mobile station and the fixed access point (AP). IEEE 802.11 networks can also have an independent configuration where the mobile stations communicate directly with one another, without support from a fixed access point.
A single-cell wireless LAN using the IEEE 802.11 Wireless LAN Standard is an Independent Basic Service Set (IBSS) network. An IBSS has an optional backbone network and consists of at least two wireless stations, as shown in FIG. 1A. A multiple-cell wireless LAN using the IEEE 802.11 Wireless LAN Standard is an Extended Service Set (ESS) network. An ESS satisfies the needs of large coverage networks of arbitrary size and complexity.
Each wireless station and access point in an IEEE 802.11 wireless LAN implements the MAC layer service, which provides the capability for wireless stations to exchange MAC frames. The MAC frame transmits management, control, or data between wireless stations and access points. After a station forms the applicable MAC frame, the frame's bits are passed to the Physical Layer for transmission.
Before transmitting a frame, the MAC layer must first gain access to the network. FIG. 1B shows three interframe space (IFS) intervals that defer an IEEE 802.11 station's access to the medium and provide various levels of priority. Each interval defines the duration between the end of the last symbol of the previous frame 113 at time T1, to the beginning of the first symbol of the next frame. The Short Interframe Space (SIFS) 115 provides the highest priority level by allowing some frames to access the medium before others, such as an Acknowledgement (ACK) frame, a Clear to Send (CTS) frame, or a subsequent fragment burst of a previous data frame. These frames require expedited access to the network to minimize frame retransmissions.
The Priority Interframe Space (PIFS) 117 of FIG. 1B is used for high priority access to the medium during the contention-free period 116 starting at T2 and ending at T3. The point coordinator 105 in the access point 108 connected to backbone network 110 in FIG. 1A controls the priority-based Point Coordination Function (PCF) to dictate which stations in cell 100 can gain access to the medium. During the contention-free period 116, station 102 in FIG. 1A, for example, is directed by the access point 108 to transmit its high priority data frame 122. The point coordinator 105 in the access point 108 sends a contention-free poll frame 120 to station 102, granting station 102 permission to transmit a single frame to any destination. Station 102 wants to transmit its high priority data frame 122 to the receiving station 106. Station 102 can transmit its frame 122 during period 116 if it senses that the medium is idle. All other stations, such as stations 104A, 104B, and 106, in the cell 100 can only transmit during contention-free period 116 if the point coordinator grants them access to the medium. In this example, stations 104A and 104B have low priority data sources 114A and 114B, and thus they must wait until the end of the contention-free period 116 at T3. This is signaled by the contention-free end frame 126 sent by the point coordinator in FIG. 1C. The contention-free end frame 126 is sent to identify the end of the contention-free period 116, which occurs when time expires or when the point coordinator has no further frames to transmit and no stations to poll.
The distributed coordination function (DCF) Interframe Space (DIFS) 119 of FIG. 1B is used by stations 104A and 104B, for example, for transmitting low priority data frames 124A and 124B, respectively, during the contention-based period 118. The DIFS spacing delays the transmission of lower priority frames 124A and 124B to occur between T3 and T4, later than the priority-based transmission of frame 122 sent by station 102. An Extended Interframe Space (EIFS) (not shown) goes beyond the time of a DIFS interval as a waiting period when a bad reception occurs. The EIFS interval provides enough time for the receiving station to send an acknowledgment (ACK) frame.
During the contention-based period 118, the distributed coordination function (DCF) uses the Carrier-Sense Multiple Access With Collision Avoidance (CSMA/CA) contention-based protocol, which is similar to IEEE 802.3 Ethernet. The CSMA/CA protocol minimizes the chance of collisions between stations sharing the medium by waiting a random backoff interval 128A or 128B of FIG. 1C, if the station's sensing mechanism indicates a busy medium. The period of time immediately following traffic on the medium is when the highest probability of collisions occurs, especially where there is high utilization. For example, stations 102, 104B, and 106 may be waiting for the medium to become idle while station 104A is transmitting, and stations 102, 104B, and 106 will attempt to transmit at the same time, once station 104A stops. Once the medium is idle, CSMA/CA protocol causes each station to delay its transmission by a random backoff time. For example, station 104B delays its transmission by a random backoff time 128B, which defers station 104B from transmitting its frame 124B, thereby minimizing the chance it will collide with those from other stations 102 and 106.
As shown in FIG. 1D, the CSMA/CA protocol computes the random backoff time 128B of station 104B as the product of a constant, the slot time, times a pseudo-random number RN which has a range of values from zero to a collision window CW. The value of the collision window for the first try to access the network by station 104B is CW1+, which yields the first try random backoff time 128B. If the first try to access the network by station 104B fails, then the CSMA/CA protocol computes a new CW by doubling the current value of CW as CW2=CW1 times 2. As shown in FIG. 1D, the value of the collision window for the second try to access the network by station 104B is CW2, which yields the second try random backoff time 128B′. This process by the CSMA/CA protocol of increasing the delay before transmission is called binary exponential backoff. The reason for increasing CW is to minimize collisions and maximize throughput for both low and high network utilization. Stations with low utilization are not forced to wait very long before transmitting their frame. On the first or second attempt, a station will make a successful transmission. However, if the utilization of the network is high, the CSMA/CA protocol delays stations for longer periods to avoid the chance of multiple stations transmitting at the same time. If the second try to access the network by station 104B fails, then the CSMA/CA protocol computes a new CW by doubling again the current value of CW as CW3=CW1 times 4. As shown in FIG. 1D, the value of the collision window for the third try to access the network by station 104B is CW3, which yields the third try random backoff time 128B″. The value of CW increases to relatively high values after successive retransmissions, under high traffic loads. This provides greater transmission spacing between stations waiting to transmit.
Collision Avoidance Techniques
Four general collision avoidance approaches have emerged: [1] Carrier Sense Multiple Access (CSMA) [see F. Tobagi and L. Kleinrock, “Packet Switching in Radio Channels: Part I—Carrier Sense Multiple Access Models and their Throughput Delay Characteristics”, IEEE Transactions on Communications, Vol 23, No 12, Pages 1400-1416, 1975], [2] Multiple Access Collision Avoidance (MACA) [see P. Karn, “MACA—A New Channel Access Protocol for Wireless Ad-Hoc Networks”, Proceedings of the ARRL/CRRL Amateur Radio Ninth Computer Networking Conference, Pages 134-140, 1990], [3] their combination CSMA/CA, and [4] collision avoidance tree expansion.
CSMA allows access attempts after sensing the channel for activity. Still, simultaneous transmit attempts lead to collisions, thus rendering the protocol unstable at high traffic loads. The protocol also suffers from the hidden terminal problem.
The latter problem was resolved by the MACA protocol, which involves a three-way handshake [P. Karn, supra]. The origin node sends a request to send (RTS) notice of the impending transmission; a response is returned by the destination if the RTS notice is received successfully; and the origin node proceeds with the transmission. This protocol also reduces the average delay as collisions are detected upon transmission of merely a short message, the RTS. With the length of the packet included in the RTS and echoed in the clear to send (CTS) messages, hidden terminals can avoid colliding with the transmitted message. However, this prevents the back-to-back re-transmission in case of unsuccessfully transmitted packets. A five-way handshake MACA protocol provides notification to competing sources of the successful termination of the transmission. [See V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A media access protocol for wireless LANs”, SIGCOMM '94, Pages 212-225, ACM, 1994.]
CSMA and MACA are combined in CSMA/CA, which is MACA with carrier sensing, to give better performance at high loads. A four-way handshake is employed in the basic contention-based access protocol used in the Distributed Coordination Function (DCF) of the IEEE 802.11 Standard for Wireless LANs. [See IEEE Standards Department, D3, “Wireless Medium Access Control and Physical Layer WG,” IEEE Draft Standard P802.11 Wireless LAN, January 1996.]
Collisions can be avoided by splitting the contending terminals before transmission is attempted. In the pseudo-Bayesian control method, each terminal determines whether it has permission to transmit using a random number generator and a permission probability “p” that depends on the estimated backlog. [See R. L. Rivest, “Network control by Bayesian Broadcast”, IEEE Trans. Inform. Theory, Vol IT 25, pp. 505-515, September 1979.]
To resolve collisions, subsequent transmission attempts are typically staggered randomly in time using the following two approaches: binary tree and binary exponential backoff.
Upon collision, the binary tree method requires the contending nodes to self-partition into two groups with specified probabilities. This process is repeated with each new collision. The order in which contending nodes transmit is determined either by serial or parallel resolution of the tree. [See J. L. Massey, “Collision-resolution algorithms and random-access communications”, in Multi-User Communication Systems, G. Longo (ed.), CISM Courses and Lectures No. 265, New York: Springer 1982, pp. 73-137.]
In the binary exponential backoff approach, a backoff counter tracks the number of pauses and hence the number of completed transmissions before a node with pending packets attempts to seize the channel. A contending node initializes its backoff counter by drawing a random value, given the backoff window size. Each time the channel is found idle, the backoff counter is decreased and transmission is attempted upon expiration of the backoff counter. The window size is doubled every time a collision occurs, and the backoff countdown starts again. [See A. Tanenbaum, Computer Networks, 3rd ed., Upper Saddle River, N.J., Prentice Hall, 1996.] The Distributed Coordination Function (DCF) of the IEEE 802.11 Standard for Wireless LANs employs a variant of this contention resolution scheme, a truncated binary exponential backoff, starting at a specified window and allowing up to a maximum backoff range below which transmission is attempted. [IEEE Standards Department, D3, supra] Different backoff counters may be maintained by a contending node for traffic to specific destinations. [Bharghavan, supra]
Quality of Service (QoS)
Quality of service (QoS) is a measure of service quality provided to a customer. The primary measures of QoS are message loss, message delay, and network availability. Voice and video applications have the most rigorous delay and loss requirements. Interactive data applications such as Web browsing have less restrained delay and loss requirements, but they are sensitive to errors. Non-real-time applications such as file transfer, Email, and data backup operate acceptably across a wide range of loss rates and delay. Some applications require a minimum amount of capacity to operate at all, for example, voice and video. Many network providers guarantee specific QoS and capacity levels through the use of Service-Level Agreements (SLAs). An SLA is a contract between an enterprise user and a network provider that specifies the capacity to be provided between points in the network that must be delivered with a specified QoS. If the network provider fails to meet the terms of the SLA, then the user may be entitled to a refund. The SLA is typically offered by network providers for private line, frame relay, ATM, or Internet networks employed by enterprises.
The transmission of time-sensitive and data application traffic over a packet network imposes requirements on the delay or delay jitter and the error rates realized; these parameters are referred to generically as the QoS (Quality of Service) parameters. Prioritized packet scheduling, preferential packet dropping, and bandwidth allocation are among the techniques available at the various nodes of the network, including access points, that enable packets from different applications to be treated differently, helping achieve the different quality of service objectives. Such techniques exist in centralized and distributed variations. The concern herein is with distributed mechanisms for multiple access in cellular packet networks or wireless ad hoc networks.
Backoff Adaptation to Traffic
Two general approaches can be employed for collision avoidance/contention resolution in a contention-based medium access protocol, the backoff approach and the probability approach. The first draws a backoff counter value from a random distribution (typically uniform) which it counts down during idle time slots; transmission is attempted when the counter expires. In the second, transmission is attempted following each idle time slot with a fixed permission probability. The two approaches can be made equivalent from a channel efficiency perspective; provided, of course, their choice of parameters is consistent.
In the pseudo-Bayesian control method, the permission probability “p” used to determine whether a terminal may attempt transmission depends on the estimated backlog. [See R. L. Rivest, “Network control by Bayesian Broadcast”, IEEE Trans. Inform. Theory, Vol IT 25, pp. 505-515, September 1979.]. Ideally, the window used to draw random backoff delays on the first transmission attempt or retransmission attempt must be appropriate for the traffic intensity and contention level at hand. The residual backoff delays should also be adapted to traffic.
With the capability for a traffic-adapted backoff delay, a different discipline may be used for adjusting the backoff window when transmission fails. While larger backoff windows values may be used initially, if transmission fails, contention persistence is increased by using a “persistence factor” less than 2 to multiply the backoff window upon transmission retrial. This enables decreasing the mean of the statistical distribution from which the new backoff counter would be selected for subsequent attempts. Transmission of newly arrived packets is postponed, thus reducing the competition for the channel and giving a better chance to aging packets to transmit successfully. The overall delay jitter is thus minimized, making this discipline a better choice for isochronous traffic.
Ideally one would want to start with a backoff counter appropriate for the traffic intensity at hand and retry upon failure with successively smaller backoff counters in order to increase the persistence of aging packets. The nodes can estimate traffic intensity from the number of failed transmission attempts, both their own and those of neighboring nodes. For the latter, each node includes the number of the retrial attempts in the messages exchanged during reservation and/or in the packet headers. As each node receives these messages, it will combine them with the retrial attempts it has experienced, assess the level of congestion, and select its initial backoff window accordingly. A shorter backoff counter is needed for lower traffic intensity.
Adaptation to traffic can be pursued for both the parameters of the backoff distribution from which backoff counters are drawn upon transmission attempt or following transmission failure, and for the adjustment of residual backoff delays. The latter is desirable in order to preserve the age ordering implicit in the backoff approach. Older packets would not be put at a disadvantage relative to new arrivals if the latter are drawn from a backoff window shortened as a result of traffic adaptation. The implicit preservation of age ordering achieved through residual backoff adaptation leads to lower delay and jitter, which are attractive for isochronous and real-time traffic streams.